#define _CRT_SECURE_NO_WARNINGS

//#include <iostream>
//using namespace std;
//
//const int N = 100010;
//int n, m;
//int a[N], b[N];
//
//void insert(int l, int r, int c)
//{
//	b[l] += c;
//	b[r + 1] -= c;
//}
//
//int main()
//{
//	scanf("%d %d", &n, &m);
//	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
//	for (int i = 1; i <= n; i++) insert(i, i, a[i]);
//
//	while (m--)
//	{
//		int l, r, c;
//		scanf("%d %d %d", &l, &r, &c);
//		insert(l, r, c);
//	}
//
//	for (int i = 1; i <= n; i++) b[i] = b[i - 1];
//	for (int i = 1; i <= n; i++) cout << b[i] << ' ';
//	cout << endl;
//
//	return 0;
//}

//
//#include <iostream>
//#include <string>
//using namespace std;
//
//int main()
//{
//	string a;
//	getline(cin, a);
//
//	size_t len = a.size();
//	for (size_t i = 0; i < len; i++)
//	{
//		size_t j = i;
//
//		while (j < len && a[j] != ' ') j++;
//
//		for (size_t k = i; k < j; k++) cout << a[k];
//		cout << endl;
//
//		i = j;
//	}
//
//	return 0;
//}

//
//#include <iostream>
//
//using namespace std;
//
//const int N = 100010;
//int n;
//int q[N];
//
//int mid_num(int* a, int l, int r)
//{
//	int mid = (l + r) >> 1;
//
//	if (a[l] > a[r])
//	{
//		if (a[r] > a[mid]) return r;
//		else if (a[l] < a[mid]) return l;
//		else mid;
//	}
//	else
//	{
//		if (a[l] > a[mid]) return l;
//		else if (a[r] < a[mid]) return r;
//		else mid;
//	}
//
//	return a[mid];
//}
//
//void quick_sort(int* a, int l, int r)
//{
//	if (l >= r) return;
//
//	int mid = mid_num(a, l, r);
//	swap(q[mid], q[l]);
//	int x = q[l], i = l - 1, j = r + 1;
//
//	while (i < j)
//	{
//		do i++; while (q[i] < x);
//		do j--; while (q[j] > x);
//		if (i < j) swap(q[i], q[j]);
//	}
//
//	quick_sort(a, l, j);
//	quick_sort(a, j + 1, r);
//}
//
//int main()
//{
//	scanf("%d", &n);
//	for (int i = 0; i < n; i++) scanf("%d", &q[i]);
//
//	quick_sort(q, 0, n - 1);
//
//	for (int i = 0; i < n; i++) cout << q[i] << ' ';
//	cout << endl;
//
//	return 0;
//}


//
//#include <iostream>
//
//using namespace std;
//
//const int N = 100010;
//int n;
//int a[N], s[N];
//
//int main()
//{
//    scanf("%d", &n);
//    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
//
//    int num = 0;
//    for (int i = 0; i < n; i++)
//    {
//        s[a[i]]++;
//        while (s[a[i]] > 1)
//        {
//            s[a[j]]--l
//                j++;
//        }
//        num = max(num, i - j + 1);
//    }
//
//    return 0;
//}